package Lee_code;

/**
 * @author blh
 * @date 2024年07月14日 17:09
 */
public class Lee_450_714 {
    int target;

    public TreeNode deleteNode(TreeNode root, int key) {
        if (root == null) {
            return root;
        }
        target = key;
        // 中序遍历是搜素二叉树的排序
        midTrace(root);
        return root;
    }

    private void midTrace(TreeNode root) {
        if (root == null) {
            return;
        }
        midTrace(root.left);
        // 操作一下
        if (root.val == target) {
            // 如果右边为空, 直接连接上左边
            if (root.right == null) {
                root = root.left;
            } // 如果右边不为空, 左边为空
            else if (root.left == null) {
                root = root.right;
            } // 如果 左边右边都不为空, 将右子树嫁接到最右边的位置
            else {
                TreeNode tempRight = root.right;
                root = root.left;
                TreeNode temp = root;
                while (temp.right != null) {
                    temp = temp.right;
                }
                temp.right = tempRight;
            }
        }
        midTrace(root.right);
    }
}
